package search;

/** 插值查找 */
public class InsertValueSearch {

  public static void main(String[] args) {

    int[] array = {1, 2, 3, 4, 4, 4, 4, 5, 6, 7, 8, 9};
    int index = insertValueSearch(array, 0, array.length - 1, 5);
    System.out.println(index);
  }

  private static int insertValueSearch(int[] array, int left, int right, int value) {

    if (left > right || value < array[0] || value > array[array.length - 1]) {
      return -1;
    }
    int mid = left + (right - left) * (value - array[left]) / (array[right] - array[left]);
    int midValue = array[mid];
    if (value < midValue) {
      return insertValueSearch(array, left, mid - 1, value);
    } else if (value > midValue) {
      return insertValueSearch(array, mid + 1, right, value);
    } else {
      return mid;
    }
  }
}
